package algo_lignes_sites.data.pre_trt.pre_trt_path;

import algo_lignes_sites.data.junction.A_Junction;
import algo_lignes_sites.data.junction.A_Junction.TypeJunction;
import algo_lignes_sites.data.junction.JunctionREF;
import algo_lignes_sites.data.path.PathREF;
import algo_lignes_sites.params.Params_ls;
import commons.logs.Logger;
import commons.spatialindex.simplegrid.SimpleGridSPI;
import commons.utils.UtilsGeom;
import commons.utils.primitive_geom.Point_d;
import commons.utils.primitive_geom.Rect_d;
import gnu.trove.set.hash.THashSet;
import java.util.ArrayList;
import java.util.HashMap;


public class PathIntersector {

	private static int nbIntersectCreee;


	// Une fois les path créés et ayant subi certaines simplifications
	// on calcule leur intersections que l'on déclare comme Junction de type INTERSECT :
	//  -> ces intersections vont être conservées pendant le traitement
	// Les SPI fournis sont pré-créés mais sans garantie de ce qu'il y a dedans ...
	// bOnlyCount = true => uniquement un calcul du nombre d'intersection
	public static int intersectPath(ArrayList<PathREF> vAllPathREF, ArrayList<JunctionREF> vAllJunctionREF, Params_ls params, SimpleGridSPI spiPath) {
		Logger.log_INFO1("-- Détermination et création des intersection entre Path --");
		spiPath.clear();
		spiPath.addObjects(vAllPathREF);

		// On doit créer un 2eme SPI aussi grand que celui pour les path, non fourni par l'appelant
		//  (on est dans le seul module qui a besoin de 2 SPI aussi grands simultanéments
		SimpleGridSPI spiJunction = new SimpleGridSPI("SPI temporaire pour junction", spiPath.getRectEmprise(), SimpleGridSPI.getTailleFor(vAllJunctionREF.size()));
		spiJunction.addObjects(vAllJunctionREF);
		nbIntersectCreee=0;

		// Tout d'abord, on stocke les rectEnglobant des différents path
		HashMap<PathREF, Rect_d> mapRectEnglob = new HashMap<PathREF, Rect_d>(vAllPathREF.size());
		for (PathREF p : vAllPathREF)
			mapRectEnglob.put(p, p.getRectEmprise());
		
		// On conserve les combinaisons Path1 / Path2 pour lesquelles un calcul d'intersection a été fait
		THashSet<String> setCombinaisonPathTraitee = new THashSet<String>();

		for (PathREF p1 : vAllPathREF) {

			Rect_d rectEnglobPath1 = mapRectEnglob.get(p1);
			
			ArrayList<PathREF> vPathProche = (ArrayList) spiPath.getObjectsThatMayIntersectWith(rectEnglobPath1);
			int nbPathProche = vPathProche.size();
			
			for (int i=0; i<nbPathProche; i++) {
				PathREF p2 = vPathProche.get(i);
				Rect_d rectEnglobPath2 = mapRectEnglob.get(p2);
				
				// test rapide si les 2 path peuvent s'intersecter
				if (rectEnglobPath1.xMax<rectEnglobPath2.xMin || rectEnglobPath1.xMin>rectEnglobPath2.xMax ||
						rectEnglobPath1.yMax<rectEnglobPath2.yMin || rectEnglobPath1.yMin>rectEnglobPath2.yMax)
					continue;

				String combinId1 = p1.id + "_" + p2.id;
				String combinId2 = p2.id + "_" + p1.id;
				if (setCombinaisonPathTraitee.contains(combinId1) || setCombinaisonPathTraitee.contains(combinId2)) continue;
				setCombinaisonPathTraitee.add(combinId1);
				setCombinaisonPathTraitee.add(combinId2);


				if (p1 == p2)
					// autointersection
					createAutoIntersection(p1, vAllJunctionREF, spiJunction);
				else
					// intersection entre 2 path
					create2PathIntersection(p1, p2, vAllJunctionREF, spiJunction, rectEnglobPath1, rectEnglobPath2);
			}
		}

		clear();

		return nbIntersectCreee;
	}

	// Détruit les objets éventuellement créés par ce module et supprime les liens statiques avec les objets passés en paramètres
	public static void clear() {
		// rien a faire
	}

	private static void createAutoIntersection(PathREF path, ArrayList<JunctionREF> vAllJunctionREF, SimpleGridSPI spiJunction) {
		ArrayList<JunctionREF> vJ = path.getVJunction();
		int nbPt = vJ.size();
		
		A_Junction path_from = path.from();
		A_Junction path_to = path.to();

		for (int i=0 ; i<nbPt-1 ; i++) {

			boolean bIntersectionAdded = false;

			JunctionREF pt1_A = vJ.get(i);
			JunctionREF pt1_B = vJ.get(i+1);
			
			double xMin_1 = Math.min(pt1_A.x, pt1_B.x);
			double xMax_1 = Math.max(pt1_A.x, pt1_B.x);
			double yMin_1 = Math.min(pt1_A.y, pt1_B.y);
			double yMax_1 = Math.max(pt1_A.y, pt1_B.y);

			for (int j=i+2 ; j<nbPt-1 ; j++) {

				JunctionREF pt2_A = vJ.get(j);
				JunctionREF pt2_B = vJ.get(j+1);
				
				// petit test simple
				if ( (pt2_A.x > xMax_1 && pt2_B.x > xMax_1) || (pt2_A.x < xMin_1 && pt2_B.x < xMin_1) ||
					 (pt2_A.y > yMax_1 && pt2_B.y > yMax_1) || (pt2_A.y < yMin_1 && pt2_B.y < yMin_1) )
					continue;

				// Cas simples où l'intersection est l'une des junctions ci-dessus
				//  -> on passe au segment suivant et on force le type INTERSECT sauf si la junction est un NODE
				// (il faut que ce soit une vraie intersection pour au moins une des partie du path (il doit etre traversant)
				if ( (pt1_A==pt2_A && (pt1_A!=path_from || pt2_A!=path_from)) ||
					 (pt1_A==pt2_B && (pt1_A!=path_from || pt2_B!=path_to)) ) {
					if (!pt1_A.isNode())
						pt1_A.setTypeJunction(TypeJunction.INTERSECT);// la junction est peut etre deja INTERSECT ...
					continue;
				} else if ( (pt1_B==pt2_A && (pt1_B!=path_to || pt2_A!=path_from)) ||
					        (pt1_B==pt2_B && (pt1_B!=path_to || pt2_B!=path_to)) ) {
					if (!pt1_B.isNode())
						pt1_B.setTypeJunction(TypeJunction.INTERSECT);// la junction est peut etre deja INTERSECT ...
					continue;
				}
				
				Point_d ptI = UtilsGeom.intersectionSegments(pt1_A, pt1_B, pt2_A, pt2_B);

				if (ptI==null)
					continue;

				if (ptI.equalsXY(pt1_A) || ptI.equalsXY(pt1_B) || ptI.equalsXY(pt2_A) || ptI.equalsXY(pt2_B))
					continue; // on veut une vraie intersection

				JunctionREF jREF = null;
				// On doit découper Path1
				// Il se pourrait que l'intersection trouvée soit déjà une junction existante
				jREF = getThisJunctionIfInTheSPI(ptI, spiJunction);
				if (jREF == null) {
					jREF = new JunctionREF(ptI.x, ptI.y, TypeJunction.INTERSECT);
					vAllJunctionREF.add(jREF);
					spiJunction.addPoint(jREF);
					nbIntersectCreee++;
				} else {
					// Junction déjà existante, on la force en INTERSECT si ce n'est deja le cas
					jREF.setTypeJunction(TypeJunction.INTERSECT);
				}
				jREF.addPathContenant(path);
				path.getVJunction().add(j+1, jREF);
				path.getVJunction().add(i+1, jREF);
				nbPt+=2;
				bIntersectionAdded = true;
				break; // on arrete la 2eme boucle et on la reprend
			}

			if (bIntersectionAdded)
				// on doit repasser sur le segment courant car les segments que l'on a manqué a cause du break ci-dessus
				// pourraient intersecter également ce segment en cours  ...
				i--;
		}
	}


	private static void create2PathIntersection(PathREF path1, PathREF path2, ArrayList<JunctionREF> vAllJunctionREF, SimpleGridSPI spiJunction,
			Rect_d rectEnglobPath1, Rect_d rectEnglobPath2) {

		ArrayList<JunctionREF> vJ1 = path1.getVJunction();
		ArrayList<JunctionREF> vJ2 = path2.getVJunction();

		int nbPt1 = vJ1.size();
		int nbPt2 = vJ2.size();

		// Pour accélérer la recherche, on fait un premier passage, grace a des tests de bounding box, pour déterminer quels segments
		//  en amont et en aval de chaque path, il n'est pas necessaire d'examiner
		// Ca limitera fortement l'aspect quadratique de l'algo
		int nbSegToSkip_amont_1, nbSegToSkip_aval_1;
		int nbSegToSkip_amont_2, nbSegToSkip_aval_2;
		JunctionREF pt_A, pt_B;
		
		nbSegToSkip_amont_1 = 0;
		pt_B = vJ1.get(0);
		for (int i=0 ; i<nbPt1-1 ; i++) {
			pt_A = pt_B;
			pt_B = vJ1.get(i+1);
			if ( (pt_A.x > rectEnglobPath2.xMax && pt_B.x > rectEnglobPath2.xMax) ||
				 (pt_A.x < rectEnglobPath2.xMin && pt_B.x < rectEnglobPath2.xMin) ||
				 (pt_A.y > rectEnglobPath2.yMax && pt_B.y > rectEnglobPath2.yMax) ||
				 (pt_A.y < rectEnglobPath2.yMin && pt_B.y < rectEnglobPath2.yMin) )
				nbSegToSkip_amont_1++;
			else
				break;
		}
		nbSegToSkip_aval_1 = 0;
		pt_B = vJ1.get(nbPt1-1);
		for (int i=nbPt1-1 ; i>0 ; i--) {
			pt_A = pt_B;
			pt_B = vJ1.get(i-1);
			if ( (pt_A.x > rectEnglobPath2.xMax && pt_B.x > rectEnglobPath2.xMax) ||
				 (pt_A.x < rectEnglobPath2.xMin && pt_B.x < rectEnglobPath2.xMin) ||
				 (pt_A.y > rectEnglobPath2.yMax && pt_B.y > rectEnglobPath2.yMax) ||
				 (pt_A.y < rectEnglobPath2.yMin && pt_B.y < rectEnglobPath2.yMin) )
				nbSegToSkip_aval_1++;
			else
				break;
		}
		
		nbSegToSkip_amont_2 = 0;
		pt_B = vJ2.get(0);
		for (int i=0 ; i<nbPt2-1 ; i++) {
			pt_A = pt_B;
			pt_B = vJ2.get(i+1);
			if ( (pt_A.x > rectEnglobPath1.xMax && pt_B.x > rectEnglobPath1.xMax) ||
				 (pt_A.x < rectEnglobPath1.xMin && pt_B.x < rectEnglobPath1.xMin) ||
				 (pt_A.y > rectEnglobPath1.yMax && pt_B.y > rectEnglobPath1.yMax) ||
				 (pt_A.y < rectEnglobPath1.yMin && pt_B.y < rectEnglobPath1.yMin) )
				nbSegToSkip_amont_2++;
			else
				break;
		}
		nbSegToSkip_aval_2 = 0;
		pt_B = vJ2.get(nbPt2-1);
		for (int i=nbPt2-1 ; i>0 ; i--) {
			pt_A = pt_B;
			pt_B = vJ2.get(i-1);
			if ( (pt_A.x > rectEnglobPath1.xMax && pt_B.x > rectEnglobPath1.xMax) ||
				 (pt_A.x < rectEnglobPath1.xMin && pt_B.x < rectEnglobPath1.xMin) ||
				 (pt_A.y > rectEnglobPath1.yMax && pt_B.y > rectEnglobPath1.yMax) ||
				 (pt_A.y < rectEnglobPath1.yMin && pt_B.y < rectEnglobPath1.yMin) )
				nbSegToSkip_aval_2++;
			else
				break;
		}


		
		// Recherche d'intersection seg / seg pour les 2 path : toutes les combin sauf les junctions éliminées ci-dessus
		int iDeb = nbSegToSkip_amont_1;
		int iFin = nbPt1-2 - nbSegToSkip_aval_1;
		
		int jDeb = nbSegToSkip_amont_2;
		int jFin = nbPt2-2 - nbSegToSkip_aval_2;
		
		for (int i=iDeb ; i<=iFin ; i++) {
			JunctionREF pt1_A = vJ1.get(i);
			JunctionREF pt1_B = vJ1.get(i+1);
			double xMin_1 = Math.min(pt1_A.x, pt1_B.x);
			double xMax_1 = Math.max(pt1_A.x, pt1_B.x);
			double yMin_1 = Math.min(pt1_A.y, pt1_B.y);
			double yMax_1 = Math.max(pt1_A.y, pt1_B.y);
			A_Junction path1_from = path1.from();
			A_Junction path1_to = path1.to();

			boolean bIntersectionAdded = false;

			for (int j=jDeb ; j<=jFin ; j++) {

				JunctionREF pt2_A = vJ2.get(j);
				JunctionREF pt2_B = vJ2.get(j+1);
				
				// petit test simple
				if ( (pt2_A.x > xMax_1 && pt2_B.x > xMax_1) || (pt2_A.x < xMin_1 && pt2_B.x < xMin_1) ||
					 (pt2_A.y > yMax_1 && pt2_B.y > yMax_1) || (pt2_A.y < yMin_1 && pt2_B.y < yMin_1) )
					continue;
				
				A_Junction path2_from = path2.from();
				A_Junction path2_to = path2.to();

				// Cas simples où l'intersection est l'une des junctions ci-dessus
				//  -> on passe au segment suivant et on force le type INTERSECT sauf si la junction est un NODE
				// (il faut que ce soit une vraie intersection pour au moins l'un des 2 path (il doit etre traversant)
				if ( (pt1_A==pt2_A && (pt1_A!=path1_from || pt2_A!=path2_from)) ||
					 (pt1_A==pt2_B && (pt1_A!=path1_from || pt2_B!=path2_to)) ) {
					if (!pt1_A.isNode())
						pt1_A.setTypeJunction(TypeJunction.INTERSECT);// la junction est peut etre deja INTERSECT ...
					continue;
				} else if ( (pt1_B==pt2_A && (pt1_B!=path1_to || pt2_A!=path2_from)) ||
					        (pt1_B==pt2_B && (pt1_B!=path1_to || pt2_B!=path2_to)) ) {
					if (!pt1_B.isNode())
						pt1_B.setTypeJunction(TypeJunction.INTERSECT);// la junction est peut etre deja INTERSECT ...
					continue;
				}
				
				Point_d ptI = UtilsGeom.intersectionSegments(pt1_A, pt1_B, pt2_A, pt2_B);

				// Si pas d'intersection, on continue
				if (ptI==null)
					continue;


				JunctionREF jREF = null;
				if ( !ptI.equalsXY(pt1_A) && !ptI.equalsXY(pt1_B) ) {
					// On doit découper Path1
					// Il se pourrait que l'intersection trouvée soit déjà une junction existante,
					//  on bien une intersection fraichement créée si intersection de 3 Path ...
					jREF = getThisJunctionIfInTheSPI(ptI, spiJunction);
					if (jREF == null) {
						jREF = new JunctionREF(ptI.x, ptI.y, TypeJunction.INTERSECT);
						vAllJunctionREF.add(jREF);
						spiJunction.addPoint(jREF);
						nbIntersectCreee++;
					} else {
						// Junction déjà existante, on la force en INTERSECT si ce n'est deja le cas
						jREF.setTypeJunction(TypeJunction.INTERSECT);
					}
					jREF.addPathContenant(path1);
					path1.getVJunction().add(i+1, jREF);
					bIntersectionAdded = true;
					nbPt1++;
					iFin++;
				}

				if ( !ptI.equalsXY(pt2_A) && !ptI.equalsXY(pt2_B) ) {
					// On doit découper Path2
					// Il se pourrait que l'intersection trouvée soit déjà une junction existante,
					//  on bien une intersection fraichement créée si intersection de 3 Path ...
					if (jREF==null) {
						jREF = getThisJunctionIfInTheSPI(ptI, spiJunction);
						if (jREF == null) {
							jREF = new JunctionREF(ptI.x, ptI.y, TypeJunction.INTERSECT);
							vAllJunctionREF.add(jREF);
							spiJunction.addPoint(jREF);
							nbIntersectCreee++;
						} else {
							// Junction déjà existante, on la force en INTERSECT si ce n'est deja le cas
							jREF.setTypeJunction(TypeJunction.INTERSECT);
						}
					}
					jREF.addPathContenant(path2);
					path2.getVJunction().add(j+1, jREF);
					bIntersectionAdded = true;
					nbPt2++;
					jFin++;
				}

				// si intersection ajoutée, on stoppe le parcours du path2, et on reprend tout le parcours du path2
				if (bIntersectionAdded)
					break;

			}

			if (bIntersectionAdded)
				// on doit repasser sur le segment courant car les segments que l'on a manqué a cause du break ci-dessus
				// pourraient intersecter également ce segment en cours  ...
				i--;
		}
	}


	private static JunctionREF getThisJunctionIfInTheSPI(Point_d pt, SimpleGridSPI spi) {
		Point_d j = spi.getPointIfInSPI(pt);
		if (j==null) return null;
		return (JunctionREF) j;
	}


}
